Laserowy bilard [A]

Limit pamięci: 256 MB

Laserowy bilard jest ostatnim krzykiem mody wśród najbardziej snobistycznej części mieszkańców Bajtocji. Stół do tej gry ma wymiary . Przy jego brzegach przymocowano bandę o szerokości , w której zamocowano par nadajników laserowych. Po włączeniu wszystkich nadajników, stół zostaje pokryty poziomymi promieniami laserowymi i pionowymi, tak że -ty promień poziomy () przecina się z -tym promieniem pionowym () w punkcie o współrzędnych . Nadajniki są od siebie niezależne, zatem można w danym momencie włączyć ich wybrany podzbiór.

Do gry w laserowy bilard używa się bili o średnicy . W momencie, gdy leżąca na stole bila przecina co najmniej jeden z promieni lasera, zapala się sygnalizator trafienia. Początkowo bila znajduje się w punkcie . Bilę wprawiono w ruch tak, że jej początkowy wektor prędkości wynosił , i pozwolono jej toczyć się bez tarcia przez jednostek czasu. W przypadku trafienia w bandę, bila odbija się idealnie sprężyście. Ile razy podczas tej operacji zapalił się sygnalizator trafienia (wliczając, potencjalnie, chwilę początkową ruchu bili)?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i () oznaczające wymiary stołu. W drugim wierszu znajduje się słowo długości złożone z liter 0 i 1: -ta litera tego słowa opisuje stan nadajnika emitującego -ty promień poziomy - litera 0 oznacza, że nadajnik jest wyłączony, zaś litera 1, że włączony. W trzecim wierszu znajduje się -literowe słowo opisujące w analogiczny sposób nadajniki dla promieni pionowych.

W czwartym wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę przypadków testowych. W kolejnych wierszach znajduje się po pięć liczb całkowitych , , , , (, , , ) wyznaczających początkową pozycję i prędkość bili oraz czas gry.

Wyjście

Na standardowe wyjście należy wypisać dokładnie wierszy, będących odpowiedziami dla kolejnych przypadków testowych. Każda odpowiedź powinna zawierać liczbę całkowitą, oznaczającą, ile razy zapalił się sygnalizator trafienia.

Przykład

Dla danych wejściowych:

4 6
1010
010110
1
5 2 1 1 8

poprawną odpowiedzią jest:

6

Autor zadania: Tomasz Idziaszek.